A storage device such as a NAND flash memory and a communication system configured to perform digital transmission need to perform an error correction process to a message being processed. To this end, a BCH (Bose-Chaudhuri-Hocquenghem) code as one of error correction codes is used. By way of example, a NAND flash memory encodes a message to be stored into a BCH code using a BCH encoder and then stores the BCH code in a memory, and decodes the BCH code read from the memory using a BCH decoder and then outputs the original message.
In general, error correction using a BCH algorithm includes generating BCH code data using the BCH encoder and then decoding the BCH code data using the BCH decoder. In this case, the BCH code data are decoded as follows. If the BCH code data are received by the BCH decoder, syndromes are calculated and an error locator polynomial is generated using the syndromes. Then, the root of the error locator polynomial is extracted to calculate the locations of error bits. In case of decoding binary BCH code data, an error can be corrected by inverting the bit value of an error bit.
The BCH decoder includes a KES (Key Equation Solver). However, the KES has limited operation speed when it is implemented in the conventional architecture. Thus, the KES module has been a major obstacle when the BCH decoder is operated at a high operation frequency and a high calculation speed. A conventional KES includes a GF (Galois Field) multiplier as illustrated in FIG. 1. Such a conventional GF multiplier includes a lot of duplicated calculation processes and has a long critical path delay. Thus, the conventional GF multiplier has a low calculation speed caused by a low operation frequency. Therefore, the conventional KES has been an impediment to implementation of a high operation speed of the BCH decoder. Further, the GF multiplier has a structure which cannot be folded and thus inevitably occupies most of the area of the KES.